public class InsertionSort {

	public static void main(String[] argv) {

		int[] list = new int[10];

		list[9] = 5;
		list[8] = 4;
		list[7] = 3;
		list[6] = 2;
		list[5] = 123;
		list[4] = 26;
		list[3] = 35;
		list[2] = 14;
		list[1] = 32;
		list[0] = 81;

		InsertionSort sort = new InsertionSort(list);

		sort.doInsertionSort();
		sort.getResult();

	}

	int[] unsortedList;

	InsertionSort(int[] list) {
		unsortedList = list;
	}

	/**
	 * average cost is n^2: the cost will be summation of i, where i goes from 1
	 * to n
	 */
	public void doInsertionSort() {

		for (int i = 1; i < unsortedList.length; i++) {
			int currentNum = unsortedList[i];

			for (int j = 0; j < i; j++) {
				if (currentNum < unsortedList[j]) {

					int k = i;
					while (k >= j) {

						if (k == j) {
							unsortedList[k] = currentNum;
							j = i;
							break;
						} else {
							k--;
							unsortedList[k + 1] = unsortedList[k];
						}
					}
				}
			}
		}
	}

	public void getResult() {
		for (int i = 0; i < unsortedList.length; i++)
			System.out.println(unsortedList[i]);
	}
}
